package demo04ArrayListLinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:咭咭熊
 * Date:2021 - 09 - 14
 * Time:16:59
 */
public class TestLinkedList {
    /***
     * 10.测试合并两个有序链表
     * @param args
     */
    public static void main(String[] args) {
        MyLinkedList myLinkedList1 = new MyLinkedList();
        myLinkedList1.addLast(10);
        myLinkedList1.addLast(22);
        myLinkedList1.addLast(28);
        myLinkedList1.addLast(52);
        myLinkedList1.addLast(53);
        myLinkedList1.display1();


        MyLinkedList myLinkedList2 = new MyLinkedList();
        myLinkedList2.addLast(1);
        myLinkedList2.addLast(12);
        myLinkedList2.addLast(58);
        myLinkedList2.addLast(92);
        myLinkedList2.addLast(99);
        myLinkedList2.display1();

        Node ret = merge(myLinkedList1.head,myLinkedList2.head);
        myLinkedList2.display2(ret);
    }
    public static Node merge(Node headA,Node headB){
        //创建一个虚拟节点
        Node prev = new Node(-1);
        //创建一个节点tmp：用于返回合并之后的新链表的头：tmp.next
        Node tmp = prev;
        //(2)当headA 和headB 都不为空的时候
        while(headA != null && headB != null) {
            if (headA.val < headB.val) {
                tmp.next = headA;
                headA = headA.next;
                tmp = tmp.next;
            }
            else{
                tmp.next = headB;
                headB = headB.next;
                tmp = tmp.next;
            }
        }
        //代码走到此处
        //如果headA为空，直接拼接headB即可
        if(headA != null){
            tmp.next = headA;
        }
        if(headB!= null){
            tmp.next = headB;
        }
        return prev.next;
    }
    /**
     * 9.在链表中找倒数第k个节点
     * @param args
     */
    public static void main9(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(10);
        myLinkedList.addLast(22);
        myLinkedList.addLast(28);
        myLinkedList.addLast(52);
        myLinkedList.addLast(26);

        Node ret = myLinkedList.findKthToTail1(3);
        System.out.println(ret.val);//28
    }
    /***
     * 8.测试链表反转
     * @param args
     */
    public static void main8(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(10);
        myLinkedList.addLast(22);
        myLinkedList.addLast(28);
        myLinkedList.addLast(52);
        myLinkedList.addLast(26);
        myLinkedList.display1();//10 22 28 52 26
        Node ret = myLinkedList.reverse1();//26 52 28 22 10
        //Node ret = myLinkedList.reverse3();//26 52 28 22 10
        myLinkedList.display2(ret);
    }
    public static void main7(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(1);
        myLinkedList.addLast(2);
        myLinkedList.addLast(3);
        myLinkedList.addLast(4);
        myLinkedList.addLast(5);
        myLinkedList.display1();
        System.out.println("=====");
    }
    public static void main6(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(1);
        myLinkedList.addLast(2);
        myLinkedList.addLast(3);
        myLinkedList.addLast(4);
        myLinkedList.addLast(5);
        myLinkedList.display1();
        myLinkedList.delete(5);
        myLinkedList.display1();
    }
    /***
     * 5.头插法和尾插法创建链表
     * 头插法——插入的元素是逆序的；
     * 尾插法——插入的元素是正序的；
     * @param args
     */
    public static void main5(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addFirst(19);
        myLinkedList.addFirst(29);
        myLinkedList.addFirst(39);
        myLinkedList.display1();//39 29 19
        myLinkedList.addLast(49);
        myLinkedList.addLast(59);
        myLinkedList.display1();//39 29 19 49 59
        System.out.println("========");
        myLinkedList.addIndex(0,110);myLinkedList.display1();//110 39 29 19 49 59
        myLinkedList.addIndex(2,120);//110 39 120 29 19 49 59
        myLinkedList.display1();
        myLinkedList.addIndex(7,222);//110 39 120 29 19 49 59 222
        myLinkedList.display1();
    }
    /***
     * 4.测试头插法
     * @param args
     */
    public static void main4(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.createLinked();
        myLinkedList.display1();// 22 23 34 42
        System.out.println("========");
        myLinkedList.addFirst( 19);//19 22 23 34 42
        myLinkedList.display1();

    }
    public static void main3(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        //调用此函数之后，就得到了当前链表的头结点；
        myLinkedList.createLinked();
        myLinkedList.display1();// 22 23 34 42
        System.out.println("========");
        int n = 4;
        Node ret = myLinkedList.findNnode(n);
        System.out.println("第" + n + "个节点的值是：" + ret.val) ;
        System.out.println("链表的长度是：" + myLinkedList.len());

        System.out.println("=========");
        System.out.println( "是否包含该元素：" + myLinkedList.contains(22));


    }
    public static void main2(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        //调用此函数之后，就得到了当前链表的头结点；
        myLinkedList.createLinked();
        myLinkedList.display1();
        System.out.println("========");

        try{
            //放的是可能出现异常的代码
            Node ret = myLinkedList.findLastNode();
            System.out.println(ret.val);
        }catch (NullPointerException e){

        }
        System.out.println("==========");

        try{
            Node ret1 = myLinkedList.findLastTwo();
            System.out.println(ret1.val);
        }catch(NullPointerException e){}
    }
/*    public static void main1(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        //调用此函数之后，就得到了当前链表的头结点；
        Node head = myLinkedList.createLinked();
        Node cur = head;
        while(cur != null){
            System.out.println(cur.val);
            cur = cur.next;
        }
    }*/
}
